The idea of the next class of automata called matrix automata abbreviated with
MA is to combine finite state automata with one automaton of the Chomsky
hierarchy of string languages. Finite state automaton for type three,
pushdown automata for type two, linear-bounded automata for type one and Turing
machines for type zero. This model was introduced in 1972 by R. Sironmoney and
K. Krithisvasan in~\cite{giftsironmoneyranisironmoney1972abstract}. At first the
formal definition of a finite state matrix automata is given.
\begin{definition}
A \emph{finite state matrix automaton} abbreviated as FSMA is a 9-tuple \\
$M = (Q, \Sigma, T, \delta, \delta', I, F, F', $\$$)$, where
\begin{compactitem}
	\item $Q = \bar{Q} \cup Q_1 \cup \ldots \cup Q_k$, $Q_i \cap Q_j = \emptyset$
	for $i \neq j$, is a finite set of states. Each $Q_i$ has an initial state
	$q_{0_i}$ and a final state $q_{e_i}$. $\bar{Q}$ has at least an initial state
	$q_0$.
	\item $\Sigma$ is a finite set of input symbols.
	\item $T$ is a finite set of stack symbols, $\left|T\right| = k$.
	\item $I = \{q_{0_1}, \ldots, q_{0_k}\}$ is the set of initial states.
	\item $F \subseteq \bar{Q}$ is the set of accepting states.
	\item $F' = \{q_{e_1}, \ldots, q_{e_k}\}$ is the set of transition states.
	\item \$ $\not\in \Sigma$ is the endmarker.
	\item
	$\delta : Q_i \times \Sigma \rightarrow 2^{Q_i \times \{\epsilon\}},
	\delta(q_{e_i}, $\$$) \in 2^{(I \cup \{q_0\}) \times \{s_i\}}$ where
	$s_i$ is the stack symbol corresponding to $Q_i, i = 1, \ldots, k$.
	\item $\delta' : \bar{Q} \times T \rightarrow 2^{\bar{Q}}$. 
\end{compactitem}
\end{definition}
A computation of $M$ works as follows: At first the input picture is extended by
endmarkers on the bottom. This row is used as the storage of the automaton.
\begin{center}
	\begin{tabular}{|ccc|}
		\hline
		$p(1, 1)$ & $\dots$    & $p(1, n)$ \\
		$\vdots$  & $\ddots$   & $\vdots$  \\
		$p(m, 1)$ & $\dots$    & $p(m, n)$ \\
		\$        & $\dots$    & \$        \\
		\hline
	\end{tabular}
\end{center}
Now $M$ reads column by column according to $\delta$ and deletes every
pixel starting at the top left corner. When it reaches the endmarker it
overwrites the \$ sign with the stack symbol of the current state set.
Afterwards it jumps to the first symbol of the next column and starts reading with the
appropriate state set. If $M$ has read the whole input picture, the storage has
$l_2(p)$ symbols.
At this point, $M$ starts reading the storage from left to right according to
$\delta'$. When $M$ reaches an accepting state after reading the storage, it
accepts the input picture.

The accepted language of a matrix automaton in this chapter is defined as
follows.
\begin{definition}
If $M$ is a FSMA, then \begin{align*} 
L(M) = \{p \in \Sigma^{*, *} \mid & (z, (1, 1), \epsilon, 1)
\overset{*}{\underset{\delta}{\vdash}} (q_0, (l_1(p) + 1, l_2(p)), y, 1) \\
&\overset{*}{\underset{\delta'}{\vdash}} (z', (l_1(p) + 1, l_2(p)), y, l_2(p))\\
&\text{ with } z \in I, z' \in F \text{ and } y \in T^+\}
\end{align*} is called the accepted language of $M$.
\end{definition}
The $4$-tupel $(z, (i, j), y, r)$ describes a configuration of $M$, where
$z$ is the current state, $(i, j)$ the position of the input pointer, $y$ the string of
the storage tape and $r$ the number of cells from the left end to the position
of the storage pointer.

We want to regard an example of a FSMA. At first, let $U$ be the language
over $\Sigma = \{., X\}$ with pictures containing the token U of $X$'s with $.$'s in
between of different size and proportion. The FSMA $M$ can be defined as follows
that $L(M) = U$ holds.
\begin{example}
$M = (Q, \{., X\}, \{T_1, T_2\}, \delta, \delta', \{q_{0_1}, q_{0_2}\}, \{q_e\}, \{q_{e_1}, q_{e_2}\}, $\$$)$\\
$Q = \bar{Q} \cup Q_1 \cup Q_2$, $\bar{Q} = \{q_0, q_1, q_e\}$,
$Q_1 = \{q_{0_1}, q_{e_1}\}$, $Q_2 = \{q_{0_2}, q_{e_2}\}$
\begin{center}
\begin{tabular}{c|c|c|c}
$\delta$  & $X$                                              & $.$                     & \$                                                       \tabularnewline
\hline
$q_{0_1}$ & ($q_{0_1}$, $\epsilon$), ($q_{e_1}$, $\epsilon$) & -                       & -                                                        \tabularnewline
\hline
$q_{e_1}$ & -                                                & -                       & ($q_{0_1}$, $T_1$), ($q_{0_2}$, $T_1$), ($q_{0}$, $T_1$) \tabularnewline
\hline
$q_{0_2}$ & ($q_{e_2}$, $\epsilon$)                          & ($q_{0_2}$, $\epsilon$) & -                                                        \tabularnewline
\hline
$q_{e_2}$ & -                                                & -                       & ($q_{0_1}$, $T_2$), ($q_{0_2}$, $T_2$), ($q_{0}$, $T_2$) \tabularnewline
\end{tabular}
\hfill
\begin{tabular}{c|c|c}
$\delta'$ & $T_1$ & $T_2$ \tabularnewline
\hline
$q_{0}$   & $q_1$ & -     \tabularnewline
\hline
$q_{1}$   & $q_e$ & $q_1$ \tabularnewline
\hline
$q_{e}$   & -     & -     \tabularnewline
\end{tabular}
\end{center}
\end{example}
In the following, it will be shown how this automaton operates with the input picture $p$. 
\begin{center}
	$p = $\begin{tabular}{|cccc|}
		\hline
		$X$ & $.$ & $.$ & $X$ \\
		$X$ & $.$ & $.$ & $X$ \\
		$X$ & $X$ & $X$ & $X$ \\
		\$  & \$  & \$  & \$  \\
		\hline
	\end{tabular}
\end{center}
At first $M$ reads the first column with the state set $Q_1$ starting in state
$q_{0_1}$. The transitions of this state are non-determinstic, thus $M$ only changes
its state to the final state $q_{e_1}$, if the input pointer reads the $X$ at
the end of the column. In state $q_{e_1}$ $M$ can only operate if it reads the
endmarker. In this case, the storage pointer is set one field to the right, the
input pointer is set to the next column, the endmarker is overridden by the
stack symbol $T_1$ and the state set is non-deterministically changed to $Q_2$
with initial state $q_{0_2}$. When $M$ reaches the bottom right corner it
overrides the endmarker and starts reading the storage from the left with the
initial state $q_0$. Now the automaton checks if the sequence of the stack
symbols are correct.
That means when $M$ reads the stack symbol $T_1$ at first, then reads several
stack symbols $T_2$ and at last the stack symbol $T_1$, $M$ accepts the input
picture.

Here you can see the derivation steps for a better illustration.
\[
\boxed{
\begin{aligned}
\begin{matrix}
q_{0_1}X & . & . & X \\[-0.5ex]
X & . & . & X \\[-0.5ex]
X & X & X & X \\[-0.5ex] 
*\$ & \$ & \$ & \$
\end{matrix}
\end{aligned}
}
\overset{*}{\underset{\delta}{\vdash}}
\boxed{
\begin{aligned}
\begin{matrix}
 & . & . & X \\[-0.5ex]
 & . & . & X \\[-0.5ex]
q_{0_1}X & X & X & X \\[-0.5ex] 
*\$ & \$ & \$ & \$
\end{matrix}
\end{aligned}
}
\underset{\delta}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
 & . & . & X \\[-0.5ex]
 & . & . & X \\[-0.5ex]
 & X & X & X \\[-0.5ex] 
q_{e_1}*\$ & \$ & \$ & \$
\end{matrix}
\end{aligned}
}
\]

\[
\underset{\delta}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
 & q_{0_2}. & . & X \\[-0.5ex]
 & . & . & X \\[-0.5ex]
 & X & X & X \\[-0.5ex] 
T_1 & *\$ & \$ & \$
\end{matrix}
\end{aligned}
}
\overset{*}{\underset{\delta}{\vdash}}
\boxed{
\begin{aligned}
\begin{matrix}
 &  &  &  \\[-0.5ex]
 &  &  &  \\[-0.5ex]
 &  &  &  \\[-0.5ex] 
T_1 & T_2 & T_2 & q_{e_1}*\$
\end{matrix}
\end{aligned}
}
\underset{\delta}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
q_0*T_1 & T_2 & T_2 & T_1
\end{matrix}
\end{aligned}
}
\]

\[
\underset{\delta'}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
T_1 & q_1*T_2 & T_2 & T_1
\end{matrix}
\end{aligned}
}
\overset{*}{\underset{\delta'}{\vdash}}
\boxed{
\begin{aligned}
\begin{matrix}
T_1 & T_2 & T_2 & q_1*T_1
\end{matrix}
\end{aligned}
}
\underset{\delta'}{\vdash}
\boxed{
\begin{aligned}
\begin{matrix}
T_1 & T_2 & T_2 & q_e*T_1
\end{matrix}
\end{aligned}
}
\]
The next thing we want to show is a formal definition of a pushdown matrix
automata.
\begin{definition}
A \emph{pushdown matrix automaton} abbreviated as PDMA is a 11-tuple \\
$M = (Q, \Sigma, T_1, T_2, \delta, \delta', I, F, F',Z_0, $\$$)$, where
\begin{compactitem}
	\item $Q = \bar{Q} \cup Q_1 \cup \ldots \cup Q_k$, $Q_i \cap Q_j = \emptyset$,
	$i \neq j$, is a finite set of states. Each $Q_i$ has an initial state
	$q_{0_i}$ and a final state $q_{e_i}$. $\bar{Q}$ has an initial state $q_0$.
	\item $\Sigma$ is a finite set of input symbols.
	\item $T_1$ is the finite set of first storage symbols, $\left|T_1\right| = k$.
	\item $T_2$ is the finite set of second storage symbols. 
	\item $I = \{q_{0_1}, \ldots, q_{0_k}\}$ is the set of initial states.
	\item $F \subseteq \bar{Q}$ is the set of accepting states.
	\item $F' = \{q_{e_1}, \ldots, q_{e_k}\}$ is the set of transition states.
	\item $Z_0 \in T_2$ is the initial symbol of the second storage.
	\item \$$ \not\in \Sigma$ is the endmarker.
	\item $\delta : Q_i \times \Sigma \rightarrow Q_i \times \{\epsilon\}$,
		$\delta(q_{e_i}, $\$$) \rightarrow (I \cup \{q_0\}) \times \{s_i\}$ where
		$s_i \in T_1$ corresponding to $Q_i$ for $i = 1, \ldots, k$.
	\item $\delta' : \bar{Q} \times (T_1 \cup \{\epsilon\}) \times T_2 \rightarrow \bar{Q} \times T_2^*$
\end{compactitem}
\end{definition}
We can see that the only difference to FSMA's is the second storage and the
control function $\delta'$. This control function is similar to the control
function of the pushdown automaton of string languages.

Conclusively, we want to show some language dependencies of MA's.
\begin{theorem}
$\familyOf{FSMA}$ is equivalent to $\familyOf{RML}$,
$\familyOf{PDMA}$ is equivalent to $\familyOf{CFML}$, 
the family of linear bounded matrix automata ($\familyOf{LBMA}$) is equivalent
to $\familyOf{CSML}$ and the family of Turing machine matrix automata
($\familyOf{TMMA}$) is equivalent to $\familyOf{PSML}$.
\end{theorem}
This can be seen in~\cite{giftsironmoneyranisironmoney1972abstract}. It is
shown that every language that is derived by right linear matrix grammar can
be accepted by a finite state matrix automata and vice versa. The other
equivalences can be shown similarly.